"""
898. 子数组按位或操作
中等
相关标签
premium lock icon
相关企业
给定一个整数数组 arr，返回所有 arr 的非空子数组的不同按位或的数量。

子数组的按位或是子数组中每个整数的按位或。含有一个整数的子数组的按位或就是该整数。

子数组 是数组内连续的非空元素序列。



示例 1：

输入：arr = [0]
输出：1
解释：
只有一个可能的结果 0 。
示例 2：

输入：arr = [1,1,2]
输出：3
解释：
可能的子数组为 [1]，[1]，[2]，[1, 1]，[1, 2]，[1, 1, 2]。
产生的结果为 1，1，2，1，3，3 。
有三个唯一值，所以答案是 3 。
示例 3：

输入：arr = [1,2,4]
输出：6
解释：
可能的结果是 1，2，3，4，6，以及 7 。


提示：

1 <= nums.length <= 5 * 104
0 <= nums[i] <= 109
"""
from typing import List


class Solution:
    def subarrayBitwiseORs(self, arr: List[int]) -> int:
        s = set()#存储为唯一
        for x,y in enumerate(arr):
            s.add(y)
            for z in range(x-1,-1,-1):
                #或子集无意义，前面是更大的父级，跳过
                if arr[z] | y == arr[z]:
                    break
                arr[z] |= y
                s.add(arr[z])
        return len(s)